package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.Arrays;

/**
 * @author: xiaomi
 * @date: 2021/4/15
 * @description: 213. 打家劫舍 II
 * https://leetcode-cn.com/problems/house-robber-ii/
 */
public class B_213_打家劫舍_II {
    static B_213_打家劫舍_II action = new B_213_打家劫舍_II();

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
        test4();
    }

    static void test1() {
        //4
        int[] nums = new int[]{1, 2, 3, 1};
        int res = action.rob(nums);
        System.out.println("res = " + res);
    }

    static void test2() {
        //3
        int[] nums = new int[]{2, 3, 2};
        int res = action.rob(nums);
        System.out.println("res = " + res);
    }

    static void test3() {
        //340
        int[] nums = new int[]{200, 3, 140, 20, 10};
        int res = action.rob(nums);
        System.out.println("res = " + res);
    }

    static void test4() {
        //42
        int[] nums = new int[]{1, 1, 3, 6, 7, 10, 7, 1, 8, 5, 9, 1, 4, 4, 3};
        int res = action.rob(nums);
        System.out.println("res = " + res);
    }

    /**
     * 每一家都有两个状态，被偷/不被偷
     * 特殊考虑环：最后判断 dp,需要留意第一间是否被偷：对偷1 的位置进行标记！
     * --这种思路居然有 BUG
     *
     * @param nums
     * @return
     */
    public int robFail(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        //0-偷；1-不偷
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = 0;
        int lastLoc = 0, count = 0;
        boolean flag = false;
        int i = 1;
        for (; i < len; i++) {
            int curLoc = -1;
            count = 0;
            dp[i][0] = dp[i - 1][1] + nums[i];
            if (lastLoc == 1) {
                curLoc = 0;
                count++;
            }
            if (dp[i - 1][0] > dp[i - 1][1]) {
                dp[i][1] = dp[i - 1][0];
                if (lastLoc == 0) {
                    curLoc = 1;
                    count++;
                }
            } else if (dp[i - 1][0] < dp[i - 1][1]) {
                dp[i][1] = dp[i - 1][1];
                if (lastLoc == 1) {
                    curLoc = 1;
                    count++;
                }
            } else {
                dp[i][1] = dp[i - 1][1];
            }
            lastLoc = curLoc;
            if (count == 2) {
                i++;
                flag = true;
                break;
            }
        }
        for (; i < len; i++) {
            dp[i][0] = dp[i - 1][1] + nums[i];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        if (flag || (lastLoc == 0 && count < 2)) {
            return dp[len - 1][1];
        } else {
            return Math.max(dp[len - 1][1], dp[len - 1][0]);
        }


    }

    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        return Math.max(getMax(0, len - 1, nums), getMax(1, len, nums));
    }

    private int getMax(int begin, int len, int[] nums) {
//        int size = len - begin;
        int[][] dp = new int[len][2];
        //0-偷
        dp[begin][0] = nums[begin];
        dp[begin][1] = 0;
        for (int i = begin + 1; i < len; i++) {
            dp[i][0] = dp[i - 1][1] + nums[i];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
//        if (begin == 0) {
//            return dp[size - 1][1];
//        } else {
//            return Math.max(dp[size - 1][1], dp[size - 1][0]);
//        }
        return Math.max(dp[len - 1][1], dp[len - 1][0]);
    }

    public int robAnswer(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }

}
